package com.shawn.datastructure.linkedlist;

public class DoublyLinkedList {

	private Node head;

	private Node tail;

	public void insertHead(int x) {
		Node newLink = new Node(x);
		if (head == null) {
			tail = newLink;
		} else {
			head.previous = newLink;
		}
		newLink.next = head;
		head = newLink;
	}

	public void insertTail(int x) {
		Node newLink = new Node(x);
		if (head == null) {
			tail = newLink;
			head = tail;
		} else {
			tail.next = newLink;
			newLink.previous = tail;
			tail = newLink;
		}
	}

	public void insertAfter(Node node, int x) {
		Node newLink = new Node(x);
		if (head == null || node == null) {
			return;
		}
		Node p = head;
		while (p != null && p != node) {
			p = p.next;
		}

		if (p == null) {
			return;
		}

		if (p.next == null) {
			insertTail(x);
			return;
		}

		newLink.next = p.next;
		newLink.previous = p;
		p.next.previous = newLink;
		p.next = newLink;

	}

	public void insertBefore(Node node, int x) {
		Node newLink = new Node(x);
		if (tail == null || node == null) {
			return;
		}
		Node p = tail;
		while (p != null && p != node) {
			p = p.previous;
		}

		if (p == null) {
			return;
		}
		if (p.previous == null) {
			insertHead(x);
			return;
		}
		newLink.next = p;
		newLink.previous = p.previous;
		p.previous.next = newLink;
		p.previous = newLink;

	}

	public void deleteHead() {
		if (head == null) {
			return;
		}
		head = head.next;
		if (head == null) {
			tail = null;
		} else {
			head.previous = null;
		}
	}

	public void deleteTail() {
		if (head == null) {
			return;
		}
		tail = tail.previous;
		if (tail == null) {
			head = null;
		} else {
			tail.next = null;
		}
	}

	public void delete(int x) {
		Node p = head;
		while (p != tail && p.value != x) {
			p = p.next;
		}

		if (p == head) {
			deleteHead();
		} else if (p == tail) {
			deleteTail();
		} else {
			p.previous.next = p.next;
			p.next.previous = p.previous;
		}
	}

	public void display() { // Prints contents of the list
		Node current = head;
		while (current != null) {
			current.displayLink();
			current = current.next;
		}
		System.out.println();
	}

	public Node findByValue(int value) {
		if (head == null) {
			return null;
		}
		Node p = head;
		while (p != null && p.value != value) {
			p = p.next;
		}
		return p;
	}

	public static void main(String args[]) {
		DoublyLinkedList myList = new DoublyLinkedList();
		myList.insertHead(13);
		myList.insertHead(7);
		myList.insertHead(10);
		myList.display(); // <-- 10(head) <--> 7 <--> 13(tail) -->

		myList.insertTail(11);
		myList.display(); // <-- 10(head) <--> 7 <--> 13 <--> 11(tail) -->

		myList.deleteTail();
		myList.display(); // <-- 10(head) <--> 7 <--> 13(tail) -->

		myList.delete(7);
		myList.display(); // <-- 10(head) <--> 13(tail) -->

		myList.deleteHead();
		myList.display(); // <-- 3(head) <--> 10 <--> 13 <--> 23 <--> 67(tail) -->

		myList.delete(13);
		myList.display(); // null

		myList.insertHead(13);
		myList.insertHead(7);
		myList.insertHead(10);
		Node node = myList.findByValue(7);
		myList.insertAfter(node, 66);
		myList.display(); // null

		Node newnode = myList.findByValue(13);
		myList.insertBefore(newnode, 22);
		myList.display(); // null

		myList.deleteTail();
		myList.display();

		myList.deleteTail();
		myList.display();

		myList.deleteHead();
		myList.display();

		myList.deleteTail();
		myList.display();

		newnode = myList.findByValue(7);
		myList.insertBefore(newnode, 22);
		myList.display();

		newnode = myList.findByValue(7);
		myList.insertAfter(newnode, 23);
		myList.display();

	}

	static class Node {

		public int value;
		public Node next;
		public Node previous;

		public Node(int value) {
			this.value = value;
		}

		public void displayLink() {
			System.out.print(value + " ");
		}
	}
}
